/*
 * main.cpp
 *
 *  Created on: Feb 7, 2013
 *      Author: grebwerd
 */
#include "Heap.h"
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <map>

int Left(int index);
int Right(int index);
int Parent(int index);
void MinHeapify(Heap heap, int index);
void BuildMinHeap(Heap heap);
int HeapMinimum(Heap heap);
int HeapExtractMinimum(Heap& heap);
void HeapDecreaseKey(Heap heap, int index, int newValue);
void MinHeapInsert(Heap& heap, int value);
char* generateRandomString();
void displayRandomString(char* randomString);
void initializeCharacterFrequencyMap();
void updateCharacterFrequencyMap(char* randomString);
void createHashMap(char* randomString);
void displayCharacterFrequency(char* randomString);

const int alphabetSize = 52;
char alphabet[alphabetSize] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y','z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
map <char, int> characterFrequencyMap;
int randomNumberOfChar;

int main() {

	char* randomString = generateRandomString();
	initializeCharacterFrequencyMap();
	displayRandomString(randomString);
	updateCharacterFrequencyMap(randomString);
	displayCharacterFrequency(randomString);
	Heap heap (characterFrequencyMap, alphabetSize);
	heap.initializeHeap();
	heap.displayNodeArray();


	//BuildMinHeap(heap);



	return 0;
}
/*
void MinHeapify(Heap heap, int index) {
	//Get the index of the left child node
	int lIndex = Left(index);
	//Get the index of the right child node
	int rIndex = Right(index);
	//variable to keep track of the index that holds the largest value
	int smallestIndex;
		if( (lIndex <= heap.arraySize) && (heap.intArray[lIndex] < heap.intArray[index]) ){
			smallestIndex = lIndex;
		}
		else{
			smallestIndex = index;
		}
		if ((rIndex <= heap.arraySize) && (heap.intArray[rIndex] < heap.intArray[smallestIndex])){
			smallestIndex = rIndex;
		}
		if (smallestIndex != index){
			//If the index didn't hold the smallest value in the array,
			//then swap the index value with the value held in the array at smallestIndex
			int temp = heap.intArray[index];
			heap.intArray[index] = heap.intArray[smallestIndex];
			heap.intArray[smallestIndex] = temp;

			//Now make sure that swapped value in the smallestIndex is smaller than it's minHeap Children
			//This call can happen at most lg n times because we are walking down a reasonably balanced binary tree.
			MinHeapify(heap, smallestIndex);
		}
}

int Left(int index){
	return (2*index+1);
}

int Right(int index){
	return (2*index+2);
}

int parent(int index){
	return((index-1)/2);
}


void BuildMinHeap(Heap heap){
	for(int i = ((heap.mapSize)/2); i>=0; i--)
		MinHeapify(heap, i);

	cout<<endl<<endl<<"The order of the new max heap is "<<endl;
	heap.display();
	cout<<endl;
}


int HeapMinimum(Heap heap){
	return heap.intArray[0];
}


int HeapExtractMinimum(Heap& heap){
	if(heap.arraySize < 1){
		cout<<"heap underflow"<<endl;
		return -1;
	}
	int min = heap.intArray[0];
	heap.intArray[0] = heap.intArray[heap.arraySize];
	heap.arraySize = heap.arraySize-1;
	MinHeapify(heap, 0);
	cout<<"HeapExtractMinimum was successful";
	cout<<"The new MinHeap is after Extracting the Min Index Value"<<endl;
	heap.display();
	return min;
}


void HeapDecreaseKey(Heap heap, int index, int newValue){
	if(newValue > heap.intArray[index]){
		cout<<"New key is larger than the current key"<<endl;
	}
	heap.intArray[index] = newValue;
	while( (index > 0) && (heap.intArray[parent(index)] > heap.intArray[index])){
		int temp = heap.intArray[index];
		heap.intArray[index] = heap.intArray[parent(index)];
		heap.intArray[parent(index)] = temp;
		index = parent(index);
	}
	cout<<"HeapDecreaseKey was successful"<<endl;
	cout<<"The new MinHeap is after decreaseing the index "<<index<<"to the value"<<newValue<<endl;
	heap.display();
}


void MinHeapInsert(Heap& heap, int value){
	heap.arraySize++;
	heap.intArray[heap.arraySize] = NULL;
	HeapDecreaseKey(heap, heap.arraySize, value);
}

*/
char* generateRandomString() {
	srand(time(NULL));
	randomNumberOfChar = (rand()%100)+1;
	char* randomString = new char[randomNumberOfChar];
	for(int i = 0; i <  randomNumberOfChar; i++){
		char randomAlphabetChar = alphabet[rand()%(alphabetSize)];
		randomString[i] = randomAlphabetChar;
	}
	return randomString;
}


void displayRandomString(char* randomString){
	cout<<"displayRandomString: ";
	int i = 0;
	while(i < randomNumberOfChar){
		cout<<randomString[i];
		i++;
	}
}

void initializeCharacterFrequencyMap() {
	int i = 0;
	while(i < alphabetSize){
		characterFrequencyMap.insert({alphabet[i],0});
		i++;
	}
}

void updateCharacterFrequencyMap(char* randomString){
	int i = 0;
	cout<<endl<<endl;
	while(i < randomNumberOfChar){
		int characterFrequency = characterFrequencyMap[randomString[i]];
		characterFrequencyMap[randomString[i]] = ++characterFrequency;
		i++;
	}
}

void displayCharacterFrequency(char* randomString){
	int i = 0;
	cout<<endl<<endl;
	while(i < randomNumberOfChar){
		cout<<"The frequency of the character "<<randomString[i]<<" is "<<characterFrequencyMap[randomString[i]]<<endl;
		i++;
	}
}


